This invention relates to apparatus and methods for managing packets in a data stream. In particular, this invention relates to apparatus and methods for managing packets in a broadband data stream.
As the Internet evolves into a worldwide commercial data network for electronic commerce and managed public data services, increasingly, customer demands have focused on the need for advanced Internet Protocol (IP) services to enhance content hosting, broadcast video and application outsourcing. To remain competitive, network operators and Internet service providers (ISPs) must resolve two main issues: meeting continually increasing backbone traffic demands and providing a suitable Quality of Service (QoS) for that traffic. Currently, many ISPs have implemented various virtual path techniques to meet the new challenges. Generally, the existing virtual path techniques require a collection of physical overlay networks and equipment. The most common existing virtual path techniques are: optical transport, asynchronous transfer mode (ATM)/frame relay (FR) switched layer, and narrowband internet protocol virtual private networks (IP VPN).
The optical transport technique is the most widely used virtual path technique. Under this technique, an ISP uses point-to-point broadband bit pipes to custom design a point-to-point circuit or network per customer. Thus, this technique requires the ISP to create a new circuit or network whenever a new customer is added. Once a circuit or network for a customer is created, the available bandwidth for that circuit or network remains static.
The ATM/FR switched layer technique provides QoS and traffic engineering via point-to-point virtual circuits. Thus, this technique does not require the creation of dedicated physical circuits or networks, as is the case with the optical transport technique. Although this technique is an improvement over the optical transport technique, this technique has several drawbacks. One major drawback of the ATM/FR technique is that this type of network is not scalable. In addition, the ATM/FR technique also requires that a virtual circuit be established every time a request to send data is received from a customer.
The narrowband IP VPN technique uses best effort delivery and encrypted tunnels to provide secured paths to the customers. One major drawback of a best effort delivery is the lack of guarantees that a packet will be delivered at all. Thus, this is not a good candidate when transmitting critical data.
Thus, it is desirable to provide apparatus and methods that reduce operating costs for service providers by collapsing multiple overlay networks into a multi-service IP backbone. In particular, it is desirable to provide apparatus and methods that allow an ISP to build the network once and sell such network multiple times to multiple customers. It is further desirable to provide apparatus and methods that efficiently manage packets in a broadband data stream.
An exemplary method for writing packets in a data stream comprises the steps of dividing a packet into long packet cells and short packet cells, storing the long packet cells in a set of long cell queues and the short packet cells in a set of short cell queues, selectively pairing a long packet cell in one of the set of long cell queues with a short packet cell in one of the set of short cell queues to obtain an optimized pair of packet cells at each write cycle, and sequentially writing the optimized pair of packet cells at each write cycle to a set of memory banks.
In one embodiment, the exemplary method for writing packets further comprises the steps of determining the data capacity of a last packet cell of the packet, assigning a first tag to the last packet cell if the data capacity is full, and assigning a second tag to the last packet cell if the data capacity is not full. The first or second tag is used for reorganizing the packet during a read cycle.
In another embodiment, the exemplary method for writing packets further comprises the steps of monitoring the long cell queues and the short cell queues and writing a stale packet cell out of order after the stale packet cell remains in a respective cell queue for a predetermined amount of time. In one embodiment, a cell index is maintained. An index difference between a top long packet cell and a top short packet cell is calculated based on the cell index and a packet stale cell is determined based on the index difference.
An exemplary method for reading packets in a data stream comprises the steps of receiving long cell requests and short cell requests, storing the long cell requests in a set of long cell request queues, storing the short cell requests in a set of short cell request queues, selectively pairing a long cell request in one of the set of long cell request queues and a short cell request in one of the set of short cell request queues to obtain an optimized pair of cell requests at each read cycle, retrieving packet cells corresponding to the optimized pair of cell requests from a set of memory banks at each read cycle, reordering the packet cells in a first data buffer, and sending the packet cells in a sequential order.
In a first embodiment, the reordering step includes the steps of assigning a tag number to each cell request, the tag number associating the cell request to a long cell request queue or a short cell request queue, and reordering the packet cells based on the tag number. In a second embodiment, the reordering step includes the steps of storing the packet cells in the first data buffer and organizing the packet cells in a sequential order in the first data buffer. In this embodiment, the organizing step includes the step of using a tag number index to reorder the packet cells in the sequential order.
In one embodiment, the exemplary method for reading packets further comprises the steps of organizing multiple packets comprising packet cells in a second data buffer and sending the multiple packets as a frame. In another embodiment, the multiple packets include packets of a first size and packets of a second size and the packets of a second size are organized and sent as a frame.
In another embodiment, the exemplary method for reading packets further comprises the steps of monitoring the long cell request queues and the short cell request queues and retrieving a packet cell corresponding to a stale cell request out of order after the stale cell request remains in a respective long cell request queue or short cell request queue for a predetermined amount of time. In one embodiment, a cell request index is maintained. An index difference between a top long cell request and a top short cell request is calculated based on the cell request index and a stale cell request is determined based on the index difference.
An exemplary apparatus for managing packets in a data stream comprises a set of buffers, each of the buffers including a long cell queue and a short cell queue, a memory access control circuit, a write request control circuit, and a read request control circuit. The write request control circuit divides a received packet into packet cells, stores each packet cell into a long cell queue or a short cell queue in the buffers, and pairs a long cell with a short cell during a write cycle. The read request control circuit receives long cell requests and short cell requests, stores each long cell request in a long cell queue and each short cell request in a short cell queue in the buffers, and pairs a long cell request with a short cell request during a read cycle. The memory access control circuit writes the packet cells from the buffers sequentially into a memory during the write cycle and reads cell data from the memory during the read cycle. In one embodiment, the memory is a double data rate SDRAM divided into multiple banks.